#include <cstdio>
#include <algorithm>
using namespace std;
typedef long long ll;
const int N=2e7+5;
int dabiao[105];
int euler[N];
ll sum[N];
int main(void){
    for(int i=1;i<N;i++){
        euler[i]=i;
    }
    for(int i=2;i<N;i++){
        if(euler[i]==i){
            for(int j=i;j<N;j+=i){
                euler[j]=euler[j]/i*(i-1);
            }
        }
    }
    sum[1]=0;
    for(int i=2;i<N;i++){
        if(i%2){
            sum[i]=sum[i-1]+euler[i]/2;
        }
        else{
            sum[i]=sum[i-1]+euler[i];
        }
    }
    int t,n;
    scanf("%d",&t);
    while(t--){
        scanf("%d",&n);
        printf("%lld\n",sum[n]);
    }
    // for(int n=1;n<100;n++){
    //     for(int i=1;i<=n;i++){
    //         for(int j=1;j<=i-1;j++){
    //             if(__gcd(i+j,i-j)==1){
    //                 dabiao[n]++;
    //             }
    //         }
    //     }
    // }
    // for(int i=1;i<20;i++){
    //     printf("%2d,",dabiao[i]);
    // }
    // printf("\n");
    // for(int i=1;i<20;i++){
    //     printf("%2d,",euler[i]);
    // }
    // printf("\n");
    return 0;
}